//
// GPSMapEdit
// (c) Konstantin Galichsky (kg@geopainting.com), 2002-2007
//
// Join elements distributed over levels to common objects.
//

# include "StdAfx.h"
# include "Resource.h"
# include "JoinRgnLevels.h"
# include "UndoRedo.h"
# include "Map.h"
# include "Types.h"
# include "MapView.h"
# include "Load.h"
# include "Status.h"
# include "fast_floor.h"
# include "Globals.h"

class CJoinRgnLevelsAction : public CEditAction {
  public:
	virtual void GetName (string_t & _str) const {_str.append ("join per-level elements");}
	virtual cu_t CanUndo () const {return cuBackup;}
	virtual bool Do ();
	virtual void Undo () {}
	virtual void Redo () {}
};

static
size_t _GetCellIndex (float _x, size_t _cCells, float _fCellSize) {
	size_t cIndex = fast_floor (_x/_fCellSize) - fast_floor (g_map.rectBound.x0/_fCellSize);
	assert (cIndex < _cCells);
	if (cIndex >= _cCells)
		cIndex = 0;

	return cIndex;
}

bool CJoinRgnLevelsAction::Do () {
	CCritSec::CLock lock (g_cs);

	if (g_map.Levels.size () < 2)
		// Nothing to do!
		return true;

	const size_t cTotalRgns = g_map.GetRgnCount ();
	if (cTotalRgns == 0)
		return true;
	size_t cRgnsProcessed = 0;

	SetStatus (GetStr (IDS_STATUS_JOINING));
	SetProgressStatus (0);

	// Determine cells size.
	assert (g_map.Levels.size () >= 2);
	float fCellSize = g_map.pTypeSet->pfGetLatGrid (g_map, g_map.Levels.size () - 2)*360.f/40000000.f;
//	360.f/(1L << g_map.Levels [g_map.Levels.size () - 2]);
	assert (fCellSize >= 0);
	size_t cCells = fast_floor (g_map.rectBound.Width ()/fCellSize) + 2;
	while (cCells > cTotalRgns/4 + 1024) {
		cCells /= 2;
		++ cCells;
		fCellSize *= 2;
	}

	size_t cKind;
	for (cKind = rkPolyline; cKind <= rkPolygon; ++ cKind) {
		rgns_t & rgns = g_map.layers [cKind].rgns;

		// Array of 'cells' to distribute objects over them to speed up rgn's search.
		// The index is proportional to element's first point's X.
		typedef std::list<std::pair<rgn_t *, size_t> > cell_t;
		std::vector<cell_t> cells (cCells);

		// Fill cells.
		rgns_t::iterator iRgn;
		for (iRgn = rgns.begin (); iRgn != rgns.end (); ++ iRgn) {
			rgn_t & rgn = * iRgn;
			if (rgn.IsDeleted () || rgn.IsWTR ())
				continue;

			const size_t cElements = rgn.elements.size ();
			for (size_t cElement = 0; cElement < cElements; ++ cElement) {
				rgn_element_t & element = rgn.elements [cElement];
				if (element.bDeleted)
					continue;

				if (element.rectBound.Invalid ())
					continue;
				const size_t cIndex = _GetCellIndex (element.rectBound.x0, cCells, fCellSize);

				cells [cIndex].push_back (std::make_pair (& rgn, cElement));
				if (cIndex > 0)
					cells [cIndex - 1].push_back (std::make_pair (& rgn, cElement));
			}
		}

		// Search for matches.
		for (iRgn = rgns.begin (); iRgn != rgns.end (); ++ iRgn) {
			rgn_t & rgn = * iRgn;
			if (rgn.IsDeleted () || rgn.IsWTR ())
				continue;

			const size_t cElements = rgn.elements.size ();
			for (size_t cElement = 0; cElement < cElements; ++ cElement) {
				rgn_element_t & element = rgn.elements [cElement];
				if (element.bDeleted)
					continue;

				if (element.rectBound.Invalid ())
					continue;
				const size_t cIndex = _GetCellIndex (element.rectBound.x0, cCells, fCellSize);

				// NOTE: save properties of 'element' because its address may change after vector resizing.
				const size_t cElementLevel = element.cLevel;
				//const points_t ElementPoints = element.points;
				const rect_t ElementRectBound = element.rectBound;

				cell_t & cell = cells [cIndex];
				for (cell_t::iterator i = cell.begin (); i != cell.end (); ++ i) {
					rgn_t & rgn2 = * (i->first);
					if (& rgn == & rgn2)
						continue;
					if (rgn2.IsDeleted () || rgn.IsWTR ())
						continue;

					if (g_bStop)
						return false;

					if (rgn.GetType () != rgn2.GetType ())
						continue;
					if (! (rgn.strLabel == rgn2.strLabel))
						continue;

					assert (i->second < rgn2.elements.size ());
					rgn_element_t & element2 = rgn2.elements [i->second];
					if (element2.bDeleted)
						continue;

					if (cElementLevel >= element2.cLevel)
						continue;

					// Compare bounding rectangles.
					const float d_max = g_map.pTypeSet->pfGetLatGrid (g_map, element2.cLevel)*360.f/40000000.f;
					// 360.f/(1L << g_map.Levels [element2.cLevel]);
					if (
						::fabs (ElementRectBound.x0 - element2.rectBound.x0) > d_max ||
						::fabs (ElementRectBound.x1 - element2.rectBound.x1) > d_max ||
						::fabs (ElementRectBound.y0 - element2.rectBound.y0) > d_max ||
						::fabs (ElementRectBound.y1 - element2.rectBound.y1) > d_max
					)
						continue;

					// Move element(s) to 'most detailed' object.
					const size_t cElements2 = rgn2.elements.size ();
					for (size_t cElement2 = 0; cElement2 < cElements2; ++ cElement2) {
						rgn_element_t & element2_old = rgn2.elements [cElement2];
						if (element2_old.bDeleted)
							continue;

						rgn.elements.push_back (rgn_element_t ());
						rgn.elements.back ().swap (element2_old);
						element2_old.bDeleted = true;
					}
					rgn.dwFlags |= rgn_t::fModified;

					// Delete former object.
					rgn2.Delete (g_map);
				}
			}

			++ cRgnsProcessed;
			SetProgressStatus (cRgnsProcessed*100/cTotalRgns);
		}
	}

	{
		cKind = rkPoint;
		rgns_t & rgns = g_map.layers [cKind].rgns;

		// Array of 'cells' to distribute objects over them to speed up the search.
		// The index is proportional to origin's point X.
		typedef std::list<std::pair<rgn_t *, size_t> > cell_t;
		std::vector<cell_t> cells (cCells);

		// Fill cells.
		rgns_t::iterator iRgn;
		for (iRgn = rgns.begin (); iRgn != rgns.end (); ++ iRgn) {
			rgn_t & rgn = * iRgn;
			if (rgn.IsDeleted () || rgn.IsWTR ())
				continue;

			const size_t cOrigins = rgn.origins.size ();
			for (size_t cOrigin = 0; cOrigin < cOrigins; ++ cOrigin) {
				rgn_origin_t & origin = rgn.origins [cOrigin];
				if (origin.bDeleted)
					continue;

				const size_t cIndex = _GetCellIndex (origin.point.x, cCells, fCellSize);

				cells [cIndex].push_back (std::make_pair (& rgn, cOrigin));
				if (cIndex > 0)
					cells [cIndex - 1].push_back (std::make_pair (& rgn, cOrigin));
			}
		}

		// Search for matches.
		for (iRgn = rgns.begin (); iRgn != rgns.end (); ++ iRgn) {
			rgn_t & rgn = * iRgn;
			if (rgn.IsDeleted () || rgn.IsWTR ())
				continue;

			const size_t cOrigins = rgn.origins.size ();
			for (size_t cOrigin = 0; cOrigin < cOrigins; ++ cOrigin) {
				rgn_origin_t & origin = rgn.origins [cOrigin];
				if (origin.bDeleted)
					continue;

				// NOTE: save properties of 'origin' because its address may change after vector resizing.
				const size_t cOriginLevel = origin.cLevel;
				const point_t OriginPoint = origin.point;

				const size_t cIndex = _GetCellIndex (origin.point.x, cCells, fCellSize);
				cell_t & cell = cells [cIndex];
				for (cell_t::iterator i = cell.begin (); i != cell.end (); ++ i) {
					rgn_t & rgn2 = * (i->first);
					if (& rgn == & rgn2)
						continue;
					if (rgn2.IsDeleted () || rgn.IsWTR ())
						continue;

					if (g_bStop)
						return false;

					if (rgn.GetType () != rgn2.GetType ())
						continue;
					if (! (rgn.strLabel == rgn2.strLabel))
						continue;

					assert (i->second < rgn2.origins.size ());
					rgn_origin_t & origin2 = rgn2.origins [i->second];
					if (origin2.bDeleted)
						continue;

					if (cOriginLevel >= origin2.cLevel)
						continue;

					// Compare points.
					const float d_max = g_map.pTypeSet->pfGetLatGrid (g_map, origin2.cLevel)*360.f/40000000.f;
					//360.f/(1L << g_map.Levels [origin2.cLevel]);
					if (
						::fabs (OriginPoint.x - origin2.point.x) > d_max ||
						::fabs (OriginPoint.y - origin2.point.y) > d_max
					)
						continue;

					// Check origin's levels are unique.
					const size_t cOrigins2 = rgn2.origins.size ();
					size_t cOrigin2;
					bool bUnique = true;
					for (cOrigin2 = 0; cOrigin2 < cOrigins2; ++ cOrigin2) {
						const size_t cLevel2 = rgn2.origins [cOrigin2].cLevel;

						for (size_t cOrigin1 = 0; cOrigin1 < cOrigins; ++ cOrigin1)
							if (rgn.origins [cOrigin1].cLevel == cLevel2) {
								bUnique = false;
								break;
							}
						if (! bUnique)
							break;
					}
					if (! bUnique)
						continue;

					// Move origin(s) to 'most detailed' object.
					for (cOrigin2 = 0; cOrigin2 < cOrigins2; ++ cOrigin2) {
						rgn_origin_t & origin2_old = rgn2.origins [cOrigin2];
						if (origin2_old.bDeleted)
							continue;

						rgn.origins.push_back (origin2_old);
						origin2_old.bDeleted = true;
					}
					rgn.dwFlags |= rgn_t::fModified;

					// Delete former object.
					rgn2.Delete (g_map);
				}
			}

			++ cRgnsProcessed;
			SetProgressStatus (cRgnsProcessed*100/cTotalRgns);
		}
	}

	g_map.RefreshDrawOrder ();

	SetStatusReady ();

	return true;
}

///////////////////////////

void JoinRgnLevels () {
	PerformEditAction (new CJoinRgnLevelsAction ());
	Refresh ();
}
